//
//  Problem813.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/9.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 813. 最大平均值和的分组
 我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

 注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

 示例:
     输入:
     A = [9,1,2,3,9]
     K = 3
     输出: 20
     解释:
     A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
     我们也可以把 A 分成[9, 1], [2], [3, 9].
     这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
     说明:

     1 <= A.length <= 100.
     1 <= A[i] <= 10000.
     1 <= K <= A.length.
     答案误差在 10^-6 内被视为是正确的。
 */
@objcMembers class Problem813: NSObject {
    func solution() {
        print(largestSumOfAverages([9,1,2,3,9], 3))
        print(largestSumOfAverages([1,2,3,4,5,6,7], 4))
        print(largestSumOfAverages([1], 1))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[len][len+1]
     2: dp[i][j]表示,从[i~n] 分成j分，得到的分数最大值
     3: dp[i][j] =
        假如：数组只有i时，nums[i] + dp[i+1]
        假如：数组有i和i+1时，(nums[i]+nums[i+1])/2 + dp[i+1]
        ... 求出最大值
     */
    func largestSumOfAverages(_ nums: [Int], _ k: Int) -> Double {
        var dp:[[Double]] = Array(repeating: Array(repeating: -1, count: nums.count+1), count: nums.count)
        
        return getDP(nums, &dp, 0, k)
    }
    
    func getDP(_ nums: [Int], _ dp: inout [[Double]], _ start: Int, _ k: Int) -> Double {
        print("start", start, k)
        if start >= nums.count || k < 0 || k > nums.count {
            return 0
        }
        if dp[start][k] != -1 {
            return dp[start][k]
        }
        if k == 1 {
            var sum = 0
            for i in start..<nums.count {
                sum += nums[i]
            }
            dp[start][k] = Double(sum) / Double(nums.count-start)
//            print(start, k, dp[start][k])
            return dp[start][k]
        }
        
        var maxValue: Double = 0
        
        var ping: Double = 0
        var sum: Int = 0
        for i in start..<nums.count {
            if nums.count - start < k {
                break
            }
            sum += nums[i]
            ping = Double(sum) / Double(i - start + 1)
            
            maxValue = max(maxValue, ping + getDP(nums, &dp, i+1, k - 1))
        }
//        print(start, k, dp[start][k])
        dp[start][k] = maxValue
        return maxValue
    }
}
